package Btree;

import java.util.*;

/**
 * All rights Reserved, Designed By www.tusdao.com
 *
 * @version V1.0
 * @Title: BTree
 * @Package myTest
 * @Description: TODO(一句话描述类是干嘛的)
 * @author: tusxxw
 * @date: 2021/3/4
 * @Copyright: 2020 www.tbs.com Inc. All rights reserved.
 * <p>
 * 注意：本内容仅限于TBS项目组内部传阅，禁止外泄以及用于其他的商业目的
 */
public class BTree {
    Node root; //根结点
    List<Node> nodeDatas; //存节点

    public void createTree(Object[] objs) {
        nodeDatas = new ArrayList<Node>();
        //创建一个个节点
        for (Object o :objs) {
            nodeDatas.add(new Node(o));
        }
        root = nodeDatas.get(0); //根结点分配内存并插入数据
        //将节点与它的左右子树相连
        for (int i=0;i< nodeDatas.size()/2;i++) {
            nodeDatas.get(i).left = nodeDatas.get(2*i+1);
            //防止数组越界
            if (i*2+2<nodeDatas.size()) {
                nodeDatas.get(i).right = nodeDatas.get(2*i+2);
            }
        }
    }
    //先序遍历
    public void prePrint(Node root) {
        if (root !=null) {
            System.out.print(root.data + " ");
            prePrint(root.left);
            prePrint(root.right);
        }
    }
    //中序遍历
    public void midPrint(Node root) {
        if (root !=null) {
            prePrint(root.left);
            System.out.print(root.data + " ");
            prePrint(root.right);
        }
    }
    //后序遍历
    public void backPrint(Node root) {
        if (root !=null) {
            prePrint(root.left);
            prePrint(root.right);
            System.out.print(root.data + " ");
        }
    }

    //层次遍历
    public void cenPrint(BTree bTree) {
        for (Node o: bTree.nodeDatas) {
            System.out.print(o.data + " ");
        }
    }

    //根据节点层次遍历 [需要用到队列，类似于BFS]
    public void cenNodePrint(Node root){
        Queue<Node> queue = new LinkedList<Node>();
        //根节点入队
        queue.offer(root);
        while(!queue.isEmpty()) {
            //出队
            Node temp = queue.poll();
            System.out.print(temp.data + " ");
            //左右孩子入队
            if (temp.left != null){
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }
        }
    }
    //先序遍历的非递归算法 算法基本思想 先输入自身的值，然后将左孩子压栈，如果左孩子为空，将右孩子压栈，左右孩子都为空弹栈
    public void preStack(Node root) {



    }


    //中序遍历的非递归算法 算法基本思想

    //后序遍历的非递归算法 算法基本思想

/*
        1
    2       3
  4  5    6   7
 8 9

 */
    public static void main(String[] args) {
        Object[] arr = {1,2,3,4,5,6,7,8,9};
        BTree bTree = new BTree();
        bTree.createTree(arr);
        System.out.println("先序遍历");
        bTree.prePrint(bTree.root);
        System.out.println("\n中序遍历");
        bTree.midPrint(bTree.root);
        System.out.println("\n后序遍历");
        bTree.backPrint(bTree.root);
        System.out.println("\n层次遍历");
        bTree.cenPrint(bTree);
        System.out.println("\n根结点的层次遍历");
        bTree.cenNodePrint(bTree.root);
    }
}

class Node{
    Node left;
    Node right;
    Object data;

    public Node(Node left, Node right, Object data) {
        this.left = left;
        this.right = right;
        this.data = data;
    }

    public Node(Object data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }

    public Node() {
    }
}
